BZOJ4514【SDOI2016】数字配对 <费用流>

Problem

【SDOI2016】数字配对

Description

有种数字，第种数字是、有个，权值是。
若两个数字满足，是的倍数，且是一个质数，那么这两个数字可以配对，并获得的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于的前提下，求最多进行多少次配对。

Input

第一行一个整数。
第二行个整数。
第三行个整数。
第四行个整数。

Output

一行一个数，最多进行多少次配对

Sample Input

Sample Output

HINT

标签：费用流

Solution

比较难想的二分图建模。
记为分解质因数后的项数（算两项），为质数的充要条件为。
可知奇偶性相同的一定不能配对，所以可建二分图，为奇在一边，为偶在另一边。
两边间连边则看是否有整除条件，流量为，费用为。
把每个点拆成左右两个点，左边与源点相连，右边与汇点相连，容量为，费用为零。
跑费用流每增广一次就判一下是否费用小于，注意最后退出的时候不要把新加入的流全退完，退一部分至刚好大于等于即可。

Code

#include <bits/stdc++.h>
#define MAX_N 300
#define MAX_M 50000
#define INF 1e16
using namespace std;
typedef long long lnt;
int n, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5];	lnt mxf, cur;
int a[MAX_N+5], f[MAX_N+5];	lnt b[MAX_N+5], c[MAX_N+5];
struct node {int v, nxt; lnt c, w;} E[MAX_M+5];
void init() {s = 0, t = n+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, lnt c, lnt w) {E[cnt] = (node){v, pr[u], c, w}, pr[u] = cnt++;}
void addedge(int u, int v, lnt c, lnt w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5], mrk[MAX_N+5];	lnt d[MAX_N+5];	int cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(cr, -1, sizeof cr), memset(d, 0, sizeof d);
    memset(mrk, false, sizeof mrk), d[s] = 0, que.push(s), inq[s] = true, mrk[s] = true;
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v;	lnt c = E[i].c, w = E[i].w;
            if (c && (!mrk[v] || d[u]+w > d[v])) {
                mrk[v] = true, d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (!mrk[t]) return false;	lnt flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, cur += d[t]*flow;
    if (cur < 0) {mxf -= cur%d[t] == 0 ? cur/d[t] : cur/d[t]+1; return false;}	return true;
}
int calc(int x) {
    int ret = 0;
    for (int i = 2; i <= x; i++)
        while (!(x%i)) x /= i, ret++;
    if (x^1) ret++;	return ret;
}
int main() {
    scanf("%d", &n), init();
    for (int i = 1; i <= n; i++) scanf("%d", a+i), f[i] = calc(a[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", b+i);
    for (int i = 1; i <= n; i++) scanf("%lld", c+i);
    for (int i = 1; i <= n; i++) if (f[i]&1) addedge(s, i, b[i], 0); else addedge(i, t, b[i], 0);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        if ((f[i]&1) && ((f[i] == f[j]+1 && a[i]%a[j] == 0) || (f[i]+1 == f[j] && a[j]%a[i] == 0)))
            addedge(i, j, INF, c[i]*c[j]);
    while (SPFA()) ;	return printf("%lld", mxf), 0;
}